import bean.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode617 {

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        return dfs(root1, root2);



    }

    /**
     * 深度优先实现
     *
     * 1.如果二者有一个为空，则直接返回另外一个节点作为合并后数的子节点
     * 2.如果二者都不为空，则直接计算二者的和，并计算依次合并左右节点
     *
     *  时间复杂度：O(min(m,n))
     *  空间复杂度：O(min(m,n))
     *
     * @param root1
     * @param root2
     * @return
     */
    TreeNode dfs(TreeNode root1, TreeNode root2){
        if (root1 == null) {
            return root2;
        }

        if (root2 == null) {
            return root1;
        }
        TreeNode mergeTree = new TreeNode();
        mergeTree.val = root1.val + root2.val;

        mergeTree.left = mergeTrees(root1.left, root2.left);
        mergeTree.right = mergeTrees(root1.right, root2.right);

        return mergeTree;
    }

    /**
     * 广度优先搜索实现
     * 广度优先搜索本质是先遍历所有同层级的节点之后，再遍历下一个层次的节点
     *
     *  具体实现方式为：分别有NodeTree：A和B
     *  1.创建A和B的对应队列，a和b
     *  2.将A和B的同一层次节点分别压入a和b
     *
     *
     * @return
     */
    TreeNode bfs(TreeNode root1, TreeNode root2){

        if (root1 == null){
            return root2;
        }

        if (root2 == null){
            return root1;
        }

        TreeNode merged = new TreeNode(root1.val + root2.val);

        Queue<TreeNode> mergedQueue = new LinkedList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();

        mergedQueue.offer(merged);
        queue1.offer(root1);
        queue2.offer(root2);

        while (!queue1.isEmpty() && !queue2.isEmpty()){
            TreeNode node = mergedQueue.poll(), node1 = queue1.poll(), node2 = queue2.poll();

            TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;

            if (left1 != null && left2 != null){
                TreeNode left = new TreeNode(left1.val + left2.val);
                node.left = left;

                mergedQueue.offer(left);
                queue1.offer(left);
                queue2.offer(right2);
            }else if (left1 == null){
                node.left = left2;
            }else if (left2 == null){
                node.left = left1;
            }

            if (right2 != null && right1 != null){
                TreeNode right = new TreeNode(right1.val + right2.val);
                node.right = right;

                mergedQueue.offer(right);
                queue1.offer(right1);
                queue2.offer(right2);
            }else if (right1 == null){
                node.right = right2;
            }else if (right2 == null){
                node.right = right1;
            }
        }

        return merged;
    }



    public static void main(String[] args) {

    }
}
